package vip.george.p0005;

public class P5 {

    /**
     * 验证是否是回文串
     *
     * @param s
     * @return
     */
    public Boolean checkPalindrome(String s) {
        int len = s.length();
        int left = 0;
        int right = len - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }


    /**
     * 方法1：
     * 暴力破解法，穷举所有子串，判断是否是回文串，然后找到最长回文串
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        int len = s.length();
        String longestPalindrome = "";
        //穷举所有的子串，以第i个字符为子串的开始字符
        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                String substring = s.substring(i, j + 1);
                if (checkPalindrome(substring) && substring.length() > longestPalindrome.length()) {
                    // 更新最长的回文字符串
                    longestPalindrome = substring;
                }
            }
        }
        return longestPalindrome;
    }


    /**
     * 方法2：
     * 中心扩展法。其核心逻辑如下：
     * 1. 初始化：记录最长回文长度和起始位置。
     * 2. 中心扩展法：
     *      对所有第i个字符，尝试两种回文形式：
     *          单中心（如 "aba"）
     *          双中心（如 "abba"）
     * 3. 更新最大值：每次找到更长回文时更新长度和起始位置。
     * 4. 返回结果：使用 substring 返回最长回文子串。
     * @param s
     * @return
     */
    public String longestPalindrome2(String s) {
        int max_length = 0; //最长回文串的长度
        int start_index = 0; //最长回文串的起始位置

        // 以s[i]为子串“中心”向左、右扩展
        for (int i = 0; i < s.length(); i++) {
            //回文串有两种形式,使用双指针时，要根据两种情况分别考虑
            //aba
            int left = i, right = i;
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                if (right - left + 1 > max_length) {
                    max_length = right - left + 1;
                    start_index = left;
                }
                left--;
                right++;
            }
            //abba
            left = i;
            right = i + 1;
            while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                if (right - left + 1 > max_length) {
                    max_length = right - left + 1;
                    start_index = left;
                }
                left--;
                right++;
            }
        }
        return s.substring(start_index, start_index + max_length);
    }

    public static void main(String[] args) {
        P5 p5 = new P5();
        System.out.println(p5.checkPalindrome("abc"));
        System.out.println(p5.checkPalindrome("abba"));
        System.out.println(p5.checkPalindrome("aaaa"));
        System.out.println(p5.checkPalindrome("abcba"));
        System.out.println("=======方法1：=======");
        System.out.println(p5.longestPalindrome("babad"));
        System.out.println(p5.longestPalindrome("cbbd"));
        System.out.println(p5.longestPalindrome("a"));
        System.out.println(p5.longestPalindrome("xaaaabbbbbbbbbbccccccccccddddddddddeeeeeeeeeeffffffffffgggggggggghhhhhhhhhhiiiiiiiiiijjjjjjjjjjkkkkkkkkkkllllllllllmmmmmmmmmmnnnnnnnnnnooooooooooppppppppppqqqqqqqqqqrrrrrrrrrrssssssssssttttttttttuuuuuuuuuuvvvvvvvvvvwwwwwwwwwwxxxxxxxxxxyyyyyyyyyyzzzzzzzzzzyyyyyyyyyyxxxxxxxxxxwwwwwwwwwwvvvvvvvvvvuuuuuuuuuuttttttttttssssssssssrrrrrrrrrrqqqqqqqqqqppppppppppoooooooooonnnnnnnnnnmmmmmmmmmmllllllllllkkkkkkkkkkjjjjjjjjjjiiiiiiiiiihhhhhhhhhhggggggggggffffffffffeeeeeeeeeeddddddddddccccccccccbbbbbbbbbbaaaaaaaabbbbbbbbbbccccccccccddddddddddeeeeeeeeeeffffffffffgggggggggghhhhhhhhhhiiiiiiiiiijjjjjjjjjjkkkkkkkkkkllllllllllmmmmmmmmmmnnnnnnnnnnooooooooooppppppppppqqqqqqqqqqrrrrrrrrrrssssssssssttttttttttuuuuuuuuuuvvvvvvvvvvwwwwwwwwwwxxxxxxxxxxyyyyyyyyyyzzzzzzzzzzyyyyyyyyyyxxxxxxxxxxwwwwwwwwwwvvvvvvvvvvuuuuuuuuuuttttttttttssssssssssrrrrrrrrrrqqqqqqqqqqppppppppppoooooooooonnnnnnnnnnmmmmmmmmmmllllllllllkkkkkkkkkkjjjjjjjjjjiiiiiiiiiihhhhhhhhhhggggggggggffffffffffeeeeeeeeeeddddddddddccccccccccbbbbbbbbbbaaaa"));
        System.out.println("========方法2：========");
        System.out.println(p5.longestPalindrome2("babad"));
        System.out.println(p5.longestPalindrome2("cbbd"));
        System.out.println(p5.longestPalindrome2("a"));
        System.out.println(p5.longestPalindrome2("xaaaabbbbbbbbbbccccccccccddddddddddeeeeeeeeeeffffffffffgggggggggghhhhhhhhhhiiiiiiiiiijjjjjjjjjjkkkkkkkkkkllllllllllmmmmmmmmmmnnnnnnnnnnooooooooooppppppppppqqqqqqqqqqrrrrrrrrrrssssssssssttttttttttuuuuuuuuuuvvvvvvvvvvwwwwwwwwwwxxxxxxxxxxyyyyyyyyyyzzzzzzzzzzyyyyyyyyyyxxxxxxxxxxwwwwwwwwwwvvvvvvvvvvuuuuuuuuuuttttttttttssssssssssrrrrrrrrrrqqqqqqqqqqppppppppppoooooooooonnnnnnnnnnmmmmmmmmmmllllllllllkkkkkkkkkkjjjjjjjjjjiiiiiiiiiihhhhhhhhhhggggggggggffffffffffeeeeeeeeeeddddddddddccccccccccbbbbbbbbbbaaaaaaaabbbbbbbbbbccccccccccddddddddddeeeeeeeeeeffffffffffgggggggggghhhhhhhhhhiiiiiiiiiijjjjjjjjjjkkkkkkkkkkllllllllllmmmmmmmmmmnnnnnnnnnnooooooooooppppppppppqqqqqqqqqqrrrrrrrrrrssssssssssttttttttttuuuuuuuuuuvvvvvvvvvvwwwwwwwwwwxxxxxxxxxxyyyyyyyyyyzzzzzzzzzzyyyyyyyyyyxxxxxxxxxxwwwwwwwwwwvvvvvvvvvvuuuuuuuuuuttttttttttssssssssssrrrrrrrrrrqqqqqqqqqqppppppppppoooooooooonnnnnnnnnnmmmmmmmmmmllllllllllkkkkkkkkkkjjjjjjjjjjiiiiiiiiiihhhhhhhhhhggggggggggffffffffffeeeeeeeeeeddddddddddccccccccccbbbbbbbbbbaaaa"));

    }
}
